翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Critical pair (term rewriting) : ウィキペディア英語版
Critical pair (logic)

In mathematical logic, a critical pair arises in term rewriting systems where rewrite rules overlap to yield two different terms.
For example, in the term rewriting system with rules
:
the only critical pair is ⟨''g''(''x'',''z''), ''f''(''x'',''z'')⟩.
When both sides of the critical pair can reduce to the same term, the critical pair is called ''convergent''. Where one side of the critical pair is identical to the other, the critical pair is called ''trivial''.
If the term rewriting system is not confluent, the critical pair may not converge, so critical pairs are potential sources where confluence will fail. In fact, the critical pair lemma states that a term rewriting system is weakly (a.k.a. locally) confluent if all critical pairs are convergent. Thus, to find out if a term rewriting system is weakly confluent, it suffices to test all critical pairs and see if they are convergent. This makes it possible to find out algorithmically if a term rewriting system is weakly confluent or not.
Weak confluence clearly implies convergent critical pairs: if any critical pair ⟨''a'', ''b''⟩ arises, then ''a'' and ''b'' have common reduct and thus the critical pair is convergent.
==See also==

*Knuth–Bendix completion, an algorithm based on critical pairs to compute a confluent and terminating term rewriting system equivalent to a given one

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Critical pair (logic)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.